#include "BTreeNode.h"
#include "Bruinbase.h"
#include <stdio.h>
#include <string.h>
using namespace std;


/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
RC rc;
if(rc = pf.read(pid,buffer) != 0) 
	{
	fprintf(stderr, "Error: cannot read the leaf node page into memory!");
	return rc;
	}
return 0; }
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
RC rc;
if(rc = pf.write(pid,buffer) != 0) 
	{
	fprintf(stderr, "Error: cannot write buffer into the leaf node page!");
	return rc;
	}
	return 0; }
	
/*
 * Change the whole buffer of characters into buffer of integers, every 4 bytes of char into 1 int value.
 */
RC BTLeafNode::convert_buffer()
{
	int i=0,j=0;
	char slot[4];
	char * p = buffer;
	while(j<PageFile::PAGE_SIZE)
	{
		memcpy(slot, p, 4);
		buffer_int[i]=atoi(slot);
		i++;
		j++;
		p+=4;
	}
}

/*
 * change the buffer of integers back into buffer of char.
 */
RC BTLeafNode::convert_back()
{
	memcpy(buffer,buffer_int,PageFile::PAGE_SIZE);
}
/*
 * Update the first element in buffer_int, which stores the number of keys.
 */
void BTLeafNode::updateTotalKeys(int count) 
{
	buffer_int[0]=count;  // always call updateTotalKeys(0) when initialize the class.
}
		
/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
// store the number of entries in the first 4 bytes in the file
	return buffer_int[0];
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	int count = getKeyCount();
	if(count==MAX_ENTRY) 
	{fprintf(stderr, "Error: this node is full!");
	return RC_NODE_FULL;}
	int eid;
	locate(key,eid);
	int temp_key;
	RecordId temp_rid;
	PageId temp_pid=getNextNodePtr();
	for(int i = count; i>=eid; i--)
	{
		readEntry(i, temp_key, temp_rid);
		writeEntry(i+1,temp_key, temp_rid);
	}
	writeEntry(eid,key,rid);
	updateTotalKeys(count+1);
	setNextNodePtr(temp_pid);
return 0; }

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	//we assume the next pointers are set already, i.e. the sibling node has been placed in the right position in the tree
	if(sibling.getKeyCount()!=0) {
	fprintf(stderr, "Error: the sibling node is not empty!");
	return RC_INVALID_NODE;}
	PageId next = getNextNodePtr();
	PageId sibling_next = sibling.getNextNodePtr();
	int eid, half1, half2;
	locate(key,eid);
	int count = getKeyCount(); //original count before inserting an entry
	if(eid<(count+1)/2) {half2 = (count+1)/2; half1 = count-half2;}
	else {half1 = (count+1)/2; half2 = count-half1;	}
	memcpy(sibling.buffer_int+1, buffer_int+(half1*3)+1, half2*3*sizeof(int)); //move the second half in the buffer_int into sibling buffer_int
	updateTotalKeys(half1);
	sibling.updateTotalKeys(half2);  //until now, half1 + half2 = original count
	setNextNodePtr(next);
	sibling.setNextNodePtr(sibling_next);
	if(eid<=half1) insert(key,rid);
	else sibling.insert(key,rid);
	siblingKey = sibling.buffer_int[3];

	//we first split into 2 nodes with the original data and original count and set the pointer right, then insert the entry into one of the nodes. The count update and pointer setting is done in the insert functions.

return 0; }

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int i=0, n = getKeyCount();
	if(n==0) 
	{fprintf(stderr, "Error: where is no entry in this node!");
	return RC_INVALID_NODE;}
	int *p=buffer_int+3;
	while(*p<searchKey && i<n)
	{
		p+=3;
		i++;
	} //now p is pointing at the insert position, i is pointing at the insert entry
	eid = i;
return 0; }

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	if (eid>=getKeyCount())
	{	fprintf(stderr, "Error: no such entry in this node! the node only has %d keys",getKeyCount());
		return RC_NO_SUCH_RECORD;
	}
	rid.pid = buffer_int[eid*3+1];
	rid.sid = buffer_int[eid*3+2];
	key = buffer_int[eid*3+3];
return 0; }

/*
 * Write the (key, rid) pair to the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[IN] the key from the entry
 * @param rid[IN] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::writeEntry(int eid, int key, RecordId rid)
{ 
	if (eid>=getKeyCount())
	{	fprintf(stderr, "Error: entry out of range!");
		return RC_NO_SUCH_RECORD;
	}
	buffer_int[eid*3+1] = rid.pid;
	buffer_int[eid*3+2] = rid.sid;
	buffer_int[eid*3+3] = key;
return 0; }

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	int n = getKeyCount();
	return buffer_int[3*n+1];
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	int n = getKeyCount();
	buffer_int[3*n+1] = pid;
return 0; }


/////////// NON LEAF /////////////
/**
 * Move pointer to the beginning of the buffer;
 */

void BTNonLeafNode::resetPtr() {
	buffer_ptr = (nl_struct*) (buffer + sizeof(int) * 2);
}

BTNonLeafNode::BTNonLeafNode() {
	resetPtr();
}

void BTNonLeafNode::updateTotalKeys(int count) {
	mempcpy(buffer, &count, sizeof(int));
}

void BTNonLeafNode::shift_r(int index){
	memcpy(buffer_ptr + 1, buffer_ptr, (getKeyCount() - index) * SLOT_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	// read first four bytes;
	char count[4];
	memcpy(count, buffer, sizeof(int));
	return atoi(count);
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	int total_keys = getKeyCount();

	if(total_keys == MAX_KEY_PER_NODE) {
		fprintf(stderr, "Cannot insert. Non-leaf node is full.");
		return RC_NODE_FULL;
	}

	resetPtr();
	int index = 0;

	while (key > buffer_ptr->key || (index != total_keys)) {
		++index;
		++buffer_ptr;
	}

	// shift all elements to the right if we don't insert at the end of the buffer
	if (index != total_keys) shift_r(index);

	// insert key & pid
	buffer_ptr->key = key;
	buffer_ptr->pid = pid;

	// update the total keys
	updateTotalKeys(total_keys + 1);

	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	RC rc;
	if((rc = insert(key, pid)) < 0)
		return rc;

	if (!sibling.getKeyCount())
		return RC_INVALID_NODE;

	int total_keys = getKeyCount();

	// middle of the node
	resetPtr();
	buffer_ptr += total_keys / 2;

	// middle key
	midKey = buffer_ptr->key;

	// copy right half to sibling
	for (int i = total_keys / 2; i < total_keys; ++i, ++buffer_ptr) {
		sibling.insert(buffer_ptr->key, buffer_ptr->pid);
	}

	// update number of keys
	updateTotalKeys(total_keys / 2);

	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	resetPtr();
	int total_keys = getKeyCount();
	int index = 0;

	while (searchKey > buffer_ptr->key || (index != total_keys)) {
		++index;
		++buffer_ptr;
	}

	pid = (--buffer_ptr)->pid;

	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	resetPtr();

	buffer_ptr->key = key;
	buffer_ptr->pid = pid2;
	(--buffer_ptr)->pid = pid1;

	return 0;
}
